package com.it.od.manual;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author: liminghui
 * @date: 2024/3/20 22:00
 * @version: 1.0
 * @description: 正整数拆分为连续正整数之和
 * // S=i+(i+1)+(i+2)+..(i+k-1)
 * =k*i+k(k-1)/2
 */
public class ContinousSum {
    public static void main(String[] args) {
        int num = 9;
        List<String> res = divide1(num);
        List<String> res2 = divide2(num);
        List<String> res3 = divide3(num);
        List<String> res4 = divide4(num);
        System.out.println(res);
        System.out.println(res2);
        System.out.println(res3);
        System.out.println(res4);
    }

    /**
     * 滑动窗口 o(n)  yyds
     *
     * @param num
     * @return
     */
    public static List<String> divide4(int num) {
        List<String> res = new ArrayList<>();
        int sum = 0;
        LinkedList<Integer> candidate = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        int left = 1;
        int right = 1;
        while (right < num) {
            sum += right;
            candidate.add(right);
            while (sum >= num) {
                if (sum == num) {
                    sb.append(num).append("=").append(candidate.stream().map(String::valueOf).collect(Collectors.joining("+")));
                    res.add(sb.toString());
                    sb.setLength(0);
                }
                sum -= left;
                left++;
                candidate.pollFirst();
            }
            right++;
        }
        return res;
    }


    /**
     * 暴力循环 o(n^2)
     *
     * @param num
     * @return
     */
    public static List<String> divide3(int num) {
        List<String> res = new ArrayList<>();
        int sum;
        List<Integer> candidate = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= num / 2; i++) { // 连续自然数的起始数
            sum = 0;
            for (int j = i; ; j++) {
                sum += j;
                candidate.add(j);
                if (sum >= num) {
                    if (sum == num) {
                        sb.append(num).append("=").append(candidate.stream().map(String::valueOf).collect(Collectors.joining("+")));
                        res.add(sb.toString());
                    }
                    candidate.clear();
                    sb.setLength(0);
                    break;
                }

            }

        }
        return res;
    }

    /**
     * 暴力破解 时间复杂度o(n^2)
     *
     * @param num
     * @return
     */
    public static List<String> divide1(int num) {
        List<String> res = new ArrayList<>();
        int sum = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= num / 2; i++) {
            for (int k = 1; ; k++) {
                sum = k * i + k * (k - 1) / 2;
                if (sum > num) {
                    break;
                }
                if (sum == num) {
                    sb.append(num).append("=");
                    for (int j = 0; j <= k - 1; j++) {
                        sb.append(i + j);
                        if (j < k - 1) {
                            sb.append("+");
                        }
                    }
                    res.add(sb.toString());
                    sb.setLength(0);
                }
            }
        }
        return res;
    }

    /**
     * 套公式
     * n(n)
     *
     * @param num
     * @return
     */
    public static List<String> divide2(int num) {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int k = 1; k <= num / 2; k++) {
            //由公式k * (2 * i + k - 1) = 2 * num知道2 * num能够被k整除
            if (2 * num % k == 0) {
                int i = (2 * num / k - k + 1) / 2;
                if (i > 0) { //能被2整除且保证第一位不为0
                    if (k > 1) { // 把整数自己排除掉
                        sb.append(num).append("=");
                        for (int j = 0; j <= k - 1; j++) {
                            sb.append(i + j);
                            if (j < k - 1) {
                                sb.append("+");
                            }
                        }
                        res.add(sb.toString());
                        sb.setLength(0);
                    }
                }
            }

        }
        return res;
    }


}
